"This site requires JavaScript to work correctly"
minimize Header

Prof. Dr. Michael Drexl

Faculty of Applied Natural Sciences and Industrial Engineering

Professors

Professor

ITC2 2.28

0991/3615-587

Sortierung:
Journal article
  • E. Prescott-Gagnon
  • G. Desaulniers
  • Michael Drexl
  • L.-M. Rousseau

European Driver Rules in Vehicle Routing with Time Windows.

In: Transportation Science vol. 44 pg. 455-473

  • (2010)

DOI: 10.1287/trsc.1100.0328

Journal article
  • Michael Drexl
  • E. Prescott-Gagnon

Labelling Algorithms for the Elementary Shortest Path Problem with Resource Constraints Considering EU Drivers’ Rules.

In: Logistics Research vol. 2 pg. 79-96

  • (2010)

DOI: 10.1007/s12159-010-0022-9

Book
  • Michael Drexl

Software zur Tourenplanung ‐ Marktstudie 2010.

Fraunhofer Verlag Stuttgart

  • (2010)
Journal article
  • Michael Drexl

Marktstudie Tourenplanungssoftware.

In: OR News (Das Magazin der Gesellschaft für Operations Research e.V.) vol. 41 pg. 6-9

  • (2011)
Journal article
  • Michael Drexl

Branch-and-Price and Heuristic Column Generation for the Generalized Truck-and-Trailer Routing Problem.

In: Journal of Quantitative Methods for Economics and Business Administration vol. 12 pg. 5-38

  • (2011)
Contribution
  • Michael Drexl
  • H. Werr

Keine Stangenware.

In: Software in der Logistik ‐ Intelligente Systeme. pg. 90-93

  • Eds.:
  • Redaktion Logistik Heute

Huss Munich

  • (2012)
Journal article
  • Michael Drexl

Synchronization in Vehicle Routing‐-A Survey of VRPs with Multiple Synchronization Constraints.

In: Transportation Science vol. 46 pg. 297-316

  • (2012)

DOI: 10.1287/trsc.1110.0400

Journal article
  • Michael Drexl

Rich Vehicle Routing in Theory and Practice.

In: Logistics Research vol. 5 pg. 47-63

  • (2012)

DOI: 10.1007/s12159-012-0080-2

Journal article
  • Michael Drexl

Applications of the Vehicle Routing Problem with Trailers and Transshipments.

In: European Journal of Operational Research vol. 227 pg. 275-283

  • (2013)

DOI: 10.1016/j.ejor.2012.12.015

Journal article
  • Michael Drexl
  • J. Rieck
  • T. Sigl
  • B. Press

Simultaneous Vehicle and Crew Routing and Scheduling for Partial- and Full-Load Long-Distance Road Transport.

In: BuR ‐ Business Research vol. 6 pg. 242-264

  • (2013)

DOI: 10.1007/BF03342751

Journal article
  • Michael Drexl

A Note on the Separation of Subtour Elimination Constraints in Elementary Shortest Path Problems.

In: European Journal of Operational Research vol. 229 pg. 595-598

  • (2013)

DOI: 10.1016/j.ejor.2013.03.009

Journal article
  • Michael Drexl

On the Generalized Directed Rural Postman Problem.

In: Journal of the Operational Research Society vol. 65 pg. 1143-1154

  • (2014)

DOI: 10.1057/jors.2013.60

Book
  • Michael Drexl

A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints.

In: Discussion Paper Series No. 1412

Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz

  • 2014 (2014)
Journal article
  • Michael Drexl

Branch-and-Cut Algorithms for the Vehicle Routing Problem with Trailers and Transshipments.

In: Networks vol. 63 pg. 119-133

  • (2014)

DOI: 10.1002/net.21526

Journal article
  • Michael Drexl
  • S. Irnich

Solving Elementary Shortest-Path Problems as Mixed-Integer Programs.

In: OR Spectrum vol. 36 pg. 281-296

  • (2014)

DOI: 10.1007/s00291-012-0302-7

Journal article
  • Michael Drexl
  • M. Schneider

A Survey of Variants and Extensions of the Location-Routing Problem.

In: European Journal of Operational Research vol. 241 pg. 283-308

  • (2015)

DOI: 10.1016/j.ejor.2014.08.030

show abstract

This is a review of the literature on variants and extensions of the standard location-routing problem published since the last survey, by Nagy and Salhi, appeared in 2006. We propose a classification of problem variants, provide concise paper excerpts that convey the central ideas of each work, discuss recent developments in the field, and list promising topics for further research.
Book
  • T. Ramsauer
  • Michael Drexl
  • J. Avenhaus-Betz

Software zur Tourenplanung ‐ Marktstudie 2015 / 2016.

Fraunhofer Verlag Stuttgart

  • (2015)
Journal article
  • A.-K. Rothenbächer
  • Michael Drexl
  • S. Irnich

Branch-and-Price-and-Cut for a Service Network Design and Hub Location Problem.

In: European Journal of Operational Research vol. 255 pg. 935-947

  • (2016)

DOI: 10.1016/j.ejor.2016.05.058

Journal article
  • C. Tilk
  • N. Bianchessi
  • Michael Drexl
  • S. Irnich
  • F. Meisel

Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem.

In: Transportation Science vol. 52 pg. 300-319

  • (2017)

DOI: 10.1287/trsc.2016.0730

show abstract

This paper presents a branch-and-price-and-cut algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The objective is to minimize a weighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-and-price-and-cut algorithm for this class of routing problems with synchronization constraints. To our knowledge, this algorithm is the first such approach that considers explicitly the temporal interdependencies between active and passive vehicles. The algorithm is based on a nontrivial network representation that models the logical relationships between the different transport tasks necessary to fulfill a request as well as the synchronization of the movements of active and passive vehicles. Second, we contribute to the development of branch-and-price methods in general, in that we solve, for the first time, an ng-path relaxation of a pricing problem with linear vertex costs by means of a bidirectional labeling algorithm. Computational experiments show that the proposed algorithm delivers improved bounds and solutions for a number of APVRP benchmark instances. It is able to solve instances with up to 76 tasks, four active, and eight passive vehicles to optimality within two hours of CPU time.
Journal article
  • M. Schneider
  • Michael Drexl

A Survey of the Standard Location-Routing Problem.

In: Annals of Operations Research vol. 259 pg. 389-414

  • (2017)

DOI: 10.1007/s10479-017-2509-0

Journal article
  • A.-K. Rothenbächer
  • Michael Drexl
  • S. Irnich

Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows.

In: Transportation Science vol. 52 pg. 1174-1190

Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz Gutenberg School of Management and Economics, Johannes-Gutenberg-Universität Mainz

  • 2016 (2018)

DOI: 10.1287/trsc.2017.0765

show abstract

In this paper, we present a new branch-and-price-and-cut algorithm to solve the truck-and-trailer routing problem with time windows (TTRPTW) and two real-world extensions. In all TTRPTW variants, the fleet consists of one or more trucks that may attach a trailer. Some customers are not accessible with a truck-and-trailer combination, but can however be serviced by one if the trailer is previously detached and parked at a suitable location. In the first extension, the planning horizon comprises two days and customers may be visited either on both days or only once, in which case twice the daily supply must be collected. The second extension incorporates load transfer times depending on the quantity moved from a truck to its trailer. The exact branch-and-price-and-cut algorithm for the standard variant and the two new extensions is based on a set-partitioning formulation in which columns are routes describing the movement of a truck and its associated trailer. Linear relaxations of this formulation are solved by column generation where new routes are generated with a dynamic programming labeling algorithm. The effectiveness of this pricing procedure can be attributed to the adaptation of techniques such as bidirectional labeling, the ng-neighborhood, and heuristic pricing using dynamically reduced networks and relaxed dominance. The cutting component of the branch-and-price-and-cut adds violated subset-row inequalities to strengthen the linear relaxation. Computational studies show that our algorithm outperforms existing approaches on TTRP and TTRPTW benchmark instances used in the literature.
Journal article
  • T. Gschwind
  • Michael Drexl

Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem.

In: Transportation Science vol. 53 pg. 480-491

  • (2019)

DOI: 10.1287/trsc.2018.0837

show abstract

In the dial-a-ride problem, user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying constraints on vehicle capacity, time windows, maximum route duration, and maximum user ride times. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. In addition, we use two optional improvement techniques: a local-search-based intraroute improvement of routes of promising solutions using the Balas–Simonetti neighborhood and the solution of a set covering model over a subset of all routes generated during the search. With these techniques, the proposed algorithm outperforms the state-of-the-art methods in terms of solution quality. New best solutions are found for several benchmark instances.
Journal article
  • C. Tilk
  • Michael Drexl
  • S. Irnich

Nested Branch-and-Price-and-Cut for Vehicle Routing Problems with Multiple Resource Interdependencies.

In: European Journal of Operational Research vol. 276 pg. 549-565

  • https://www.sciencedirect.com/science/article/abs/pii/S0377221719300761 (2019)

DOI: 10.1016/j.ejor.2019.01.041

show abstract

This paper considers vehicle routing problems (VRPs) with multiple resource interdependencies and addresses the development and computational evaluation of an exact branch-and-price-and-cut algorithm for their solution. An interdependency between two resources means that the two resource consumptions influence one another in such a way that a tradeoff exists between them. This impacts the feasibility and/or the cost of a solution. The subproblem in branch-and-price-and-cut procedures for VRPs is very often a variant of the shortest-path problem with resource constraints (SPPRC). For the exact solution of many SPPRC variants, dynamic-programming based labeling algorithms are predominant. The tradeoffs in problems with multiple resource interdependencies, however, render the application of labeling algorithms unpromising. This is because complex data structures for managing the tradeoff curves are necessary and only weak dominance criteria are possible, so that the labeling algorithm becomes almost a pure enumeration. Therefore, we propose to solve also the SPPRC subproblem with branch-and-price-and-cut. This results in a two-level, nested branch-and-price-and-cut algorithm. We analyze different variants of the algorithm to enable the exchange of columns and also rows between the different levels. To demonstrate the computational viability of our approach, we perform computational experiments on a prototypical VRP with time windows, minimal and maximal delivery quantities for each customer, a customer-dependent profit paid for each demand unit delivered, and temporal synchronization constraints between some pairs of customers. In this problem, tradeoffs exist between cost and load and between cost and time.
Journal article
  • N. Bianchessi
  • Michael Drexl
  • S. Irnich

The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints.

In: Transportation Science vol. 53 pg. 1067-1084

  • (2019)

DOI: 10.1287/trsc.2018.0862

show abstract

In classical routing problems, each customer is visited exactly once. By contrast, when allowing split deliveries, customers may be served through multiple visits. This potentially results in substantial savings in travel costs. Even if split deliveries are beneficial to the transport company, several visits may be undesirable on the customer side: At each visit the customer has to interrupt his primary activities and handle the goods receipt. The contribution of the present paper consists in a thorough analysis of the possibilities and limitations of split delivery distribution strategies. To this end, we investigate two different types of measures for limiting customer inconvenience (a maximum number of visits and the temporal synchronization of deliveries) and evaluate the impact of these measures on carrier efficiency by means of different objective functions (comprising variable routing costs, costs related to route durations, and fixed fleet costs). We consider the vehicle routing problem with time windows in which split deliveries are allowed (SDVRPTW) and define the corresponding generalization that takes into account customer inconvenience constraints (SDVRPTW-IC). We design an extended branch-and-cut algorithm to solve the SDVRPTW-IC and report on experimental results showing the impact of customer inconvenience constraints. We finally draw useful insights for logistics managers on the basis of the experimental analysis carried out.
Journal article
  • Michael Drexl

On the one-to-one pickup-and-delivery problem with time windows and trailers.

In: Central European Journal of Operations Research vol. 29 pg. 1115-1162

  • (2021)

DOI: 10.1007/s10100-020-00690-w

show abstract

This paper studies an extension of the well-known one-to-one pickup-and-delivery problem with time windows. In the latter problem, requests to transport goods from pickup to delivery locations must be fulfilled by a set of vehicles with limited capacity subject to time window constraints. Goods are not interchangeable: what is picked up at one particular location must be delivered to one particular other location. The discussed extension consists in the consideration of a heterogeneous vehicle fleet comprising lorries with detachable trailers. Trailers are advantageous as they increase the overall vehicle capacity. However, some locations may be accessible only by lorries. Therefore, special locations are available where trailers can be parked while lorries visit accessibility-constrained locations. This induces a nontrivial tradeoff between an enlarged vehicle capacity and the necessity of scheduling detours for parking and reattaching trailers. The contribution of the paper is threefold: (i) it studies a practically relevant generalization of the one-to-one pickup-and-delivery problem with time windows. (ii) It develops an exact amortized constant-time procedure for testing the feasibility of an insertion of a transport task into a given route with regard to time windows and lorry and trailer capacities. (iii) It provides a comprehensive set of new benchmark instances on which the runtime of the constant-time test is compared with a naïve one that requires linear time by embedding both tests in an adaptive large neighbourhood search algorithm. Computational experiments show that the constant-time test outperforms its linear-time counterpart by one order of magnitude on average.
Journal article
  • Michael Drexl

On efficient testing of capacity constraints in pickup-and-delivery problems with trailers.

In: 4OR - A Quarterly Journal of Operations Research vol. 19 pg. 289-307

  • (2021)

DOI: 10.1007/s10288-020-00452-z

show abstract

Efficient feasibility tests are important in many heuristics for routing problems. This paper considers several variants of pickup-and-delivery problems with trailers. Its contribution consists in the description of constant-time procedures for testing observance of capacity constraints when inserting tasks into routes. It is demonstrated that the presence of vehicles with detachable trailers makes capacity feasibility tests considerably more involved.